/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-02-09
 * Time: 9:49
 */
public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public  TreeNode(int val){
            this.val=val;
        }
    }
    public TreeNode root=null;//根节点

    //查找二叉搜索树中指定的val的值
    public TreeNode find(int val){
        if(root==null){
            return null;
        }
        TreeNode cur=root;
        while(cur!=null) {
            if (cur.val == val) {
                return cur;
            } else if (cur.val < val) {
                cur = cur.right;
            } else if (cur.val > val) {
                cur = cur.left;
            }
        }
        return null;
    }

    //插入操作，最后肯定都是插到了叶子节点
    //定义2个，一个标识结点现在的位置，一个标识它的父节点
    public void insert(int val){
        if(root==null){
            //这个二叉树为空时
            root=new TreeNode(val);
            return;
        }
        //不为空时
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }else if(cur.val==val){
                //在二叉搜索树里面，不会出现一个数出现2次的情况，如果遇到相等就不插入
                return;
            }
        }

        //cur==null了
        if(parent.val<val){
            parent.right=new TreeNode(val);
        }else{
            parent.left=new TreeNode(val);
        }
    }


    //写个中序遍历，遍历出来的一定是有序的
    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    //删除操作
    //删除值为val的结点
    public void remove(int val){
        TreeNode cur=root;
        TreeNode parent=null;
        while(cur!=null){
            if(cur.val==val){
                //这里执行删除操作
                removeNode(parent,cur);//alt+回车，可以创建方法
                return;
            }else if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else{
                parent=cur;
                cur=cur.left;
            }
        }
    }
    //这里执行删除操作
    private void removeNode(TreeNode parent,TreeNode cur){
        if(cur.left==null){
            if(cur==root){
                root=cur.right;
            }else if(cur!=root && parent.left==cur){
                parent.left=cur.right;
            }else if(cur!=root && parent.right==cur){
                parent.right=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=cur.left;
            }else if(cur!=root && parent.left==cur){
                parent.left=cur.left;
            }else if(cur!=root && parent.right==cur){
                parent.right=cur.left;
            }
        }else{
            //cur.left!=null && cur.right!=null
            //替换删除的方法
            //在找到的这个要删除的结点cur以后，  去找它的左子树的最大值，就是这个结点的  左孩子的右孩子  一直到右孩子是null为止
            // 或者去找它的右子树的最小值来替换这个位置,就是这个结点的  右孩子的左孩子  一直到左孩子是null为止---->以这个为例来写这次的代码
            //然后把找到的这个结点target的值来覆盖原来要删除的结点cur的值 ,, 并且删掉在其左树或者右树找到的这个target结点
            TreeNode target=cur.right;
            TreeNode targetParent=cur;
            while(target.left!=null){
                targetParent=target;
                target=target.left;
            }
            //target.left==null时
            cur.val=target.val;
            //就应该来删除target这个位置了----》target没有左孩子了，
            if(targetParent.left==target){
                targetParent.left=target.right;
            }else{
                // targetParent.right==target
                targetParent.right=target.right;
            }
        }
    }
}
